#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define  NOTFOUND -2
#define  FOUND -1

int logN(unsigned int s);
int numOfUnplacedFruits(int* fruits, int fruitsSize, int* baskets,int basketsSize);
void buildSegmentTree(int *arr,int *tree,int left,int right);
int * buildSegmentTree2(int *arr,int size,int *ts);
int findLeftMost(int *,int ,int ,int);


int logN(unsigned int s){
    int r=1,k=0;
    while( r<s ){
        k++;
        r+=r;
    }
    return k;
}

int Pow(int a,int b){
    if( b==0 )return 1;
    int s=a;
    for(int i=1;i<b;i++)
        s+=s;
    return s;
}

int * buildSegmentTree2(int *arr,int size,int *treeSize){
    int n=logN(size);
    int sz=Pow(2,n+1);
    int offset=Pow(2,n);
    int *ret=malloc(sizeof(int)*sz);
    for( int i=0; i<offset; i++ )
        if( i >= size )
            ret[ i+offset ]=-1;
        else
            ret[ i+offset ]=arr[i];
    for( int i=(sz-1)/2; i>0 ; i-- ){
        ret[i]=ret[2*i]>ret[2*i+1]?ret[2*i]:ret[2*i+1];
    }
    *treeSize=sz;
    return ret;
}

int numOfUnplacedFruits(int* fruits, int fruitsSize, int* baskets,int basketsSize){
    int ts;
    int *segmentTree=buildSegmentTree2( baskets,basketsSize,&ts );
    /*
    for(int i=1;i<ts;i++)
        printf("%d ",segmentTree[i]);
    printf("\n");*/
    int r=0;
    for( int i=0; i < fruitsSize; i++ ){
        for(int i=1; i<ts; i++)
            printf("%d ",segmentTree[i]);
        printf("\n");
        if( findLeftMost( segmentTree,ts,1,fruits[i] ) == NOTFOUND ){
            r++;
        }
    }
    return r;
}
int findLeftMost(int * sT,int size,int pos,int val){
    int tmp1,tmp2;
    if( pos >= size )   
        return NOTFOUND;
    else if( val > sT[pos] ){
        printf("val :%d sT[pos]:%d pos:%d\n",val,sT[pos],pos);
        return NOTFOUND;
    }
    else if( 2*pos >= size ){   //  leaf node
        sT[pos]=-1;
        return FOUND;
    }
    else if( (tmp1=findLeftMost(sT,size,2*pos,val))  == NOTFOUND ){
        tmp2=findLeftMost(sT,size,2*pos+1,val);
        sT[pos]=sT[2*pos]>sT[2*pos+1]?sT[2*pos]:sT[2*pos+1];
        return FOUND;
    }else{
        sT[pos]=sT[2*pos]>sT[2*pos+1]?sT[2*pos]:sT[2*pos+1];
        return FOUND;
    }
}
int main(){
    int fruits[] = {4,2,5},baskets[] = {3,5,4};
    printf("%d\n", numOfUnplacedFruits( fruits, sizeof(fruits)/sizeof(int), baskets, sizeof(baskets)/sizeof(int) ));
    return 0;
}
